// https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
// Created by ade on 2022/9/20.
// 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
// [7628,3147,7137,2578,7742,2746,4264,7704,9532,9679,8963,3223,2133,7792,5911,3979]
//6
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int avg = 0;
    int len = 0;
    bool flag = false;

//    bool canPartitionKSubsets1(vector<int> &nums, int k) {
//        int sum = accumulate(nums.begin(), nums.end(), 0);
//        if (sum % k != 0) return false;
//        avg = sum / k;
//        len = nums.size();
//        vector<int> vi(len, 0);
//        sort(nums.begin(), nums.end());
//        dfs(nums, 0, k, vi, len);
//        for (int i = 0; i < len; i++) {
//            vector<int> vi(len, 0);
//            vi[i] = 1;
//            dfs(nums, nums[i], k, vi, len - 1);
//            vi[i] = 0;
//            cout << "flag:" << flag << endl;
//            if (flag) return true;
//        }

//        return flag;
//    }

    /**
     *
     * @param nums
     * @param sum
     * @param tmp 当前存入的index集合
     * 这种不剪枝的方式会导致时间空间复杂度爆炸
     */
//    void dfs(vector<int> &nums, int sum, int k, vector<int> &vi, int vi_left_count) {
//        if (sum == avg) {
//            k--;
//            sum = 0;
//            if (k < 0) return;
//            if (vi_left_count == 0) {
//                if (k == 0)
//                    flag = true;
//                return;
//            }
//        }
//        for (int i = 0; i < len; i++) {
//            if (vi[i] == 1) continue;
//            if (sum + nums[i] <= avg) {
//                vi[i] = 1;
//                dfs(nums, sum + nums[i], k, vi, vi_left_count - 1);
//                vi[i] = 0;
//            }
//        }
//    }

    bool canPartitionKSubsets(vector<int> &nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        avg = sum / k;
        len = nums.size();
        sort(nums.rbegin(), nums.rend());
        if (nums[0] > avg) return false;

        vector<int> bucket(k, 0);
        dfs1(nums, bucket, 0, k);
        return flag;
    }

    void dfs1(vector<int> &nums, vector<int> &bucket, int index, int k) {
        if (index == len) {
            flag = true;
            return;
        };
        for (int i = 0; i < k; i++) {
            // 桶排序，如果当前桶和前一个桶的高度相同，则i++,这一步骤至关重要
            if (bucket[i] + nums[index] > avg || (i && bucket[i - 1] == bucket[i])) continue;
            bucket[i] += nums[index];
            dfs1(nums, bucket, index + 1, k);
            bucket[i] -= nums[index];
        }
    }
};

int main() {
    vector<int> nums = {3522, 181, 521, 515, 304, 123, 2512, 312, 922, 407, 146, 1932, 4037, 2646, 3871, 269};
    int k = 5;
    Solution so;
    cout << so.canPartitionKSubsets(nums, k);
    return 0;
}